home *** CD-ROM | disk | FTP | other *** search
/ Aminet 7 / Aminet 7 - August 1995.iso / Aminet / docs / misc / ConcNews.lha / news / general.programming / comp.programming_2014_000026.msg < prev    next >
Encoding:
Text File  |  1994-11-27  |  2.8 KB  |  59 lines
  1. Newsgroups: comp.programming
  2. Path: dd.chalmers.se!news.chalmers.se!sunic!pipex!uunet!mnemosyne.cs.du.edu!nyx10!colin
  3. From: colin@nyx10.cs.du.edu (Colin Plumb)
  4. Subject: Re: Data structure for a Text Editor
  5. Message-ID: <1994Apr13.102452.15600@mnemosyne.cs.du.edu>
  6. X-Disclaimer: Nyx is a public access Unix system run by the University
  7.      of Denver for the Denver community.  The University has neither
  8.      control over nor responsibility for the opinions of users.
  9. Sender: usenet@mnemosyne.cs.du.edu (netnews admin account)
  10. Organization: Nyx, Public Access Unix at U. of Denver Math/CS dept.
  11. References: <2o5u6r$apr@scratchy.reed.edu>
  12. Distribution: na
  13. Date: Wed, 13 Apr 94 10:24:52 GMT
  14. Lines: 43
  15.  
  16. In article <2o5u6r$apr@scratchy.reed.edu>,
  17. Douglas Squirrel <dsquirre@reed.edu> wrote:
  18. >I am writing a text editor on the Macintosh in Think C.
  19. >The text is likely to be large (often over 400K, peak about 800K).
  20. >Editing will be minimal, but viewing will be the main use.  That is, editing
  21. >should be quick, but viewing should be quicker, even at the expense of edit 
  22. >speed.
  23. >Memory will not be a big concern (but it would be nice to avoid being a hog).
  24. >
  25. >I am using a linked list of lines terminated by newlines.  The linked list
  26. >will actually be a balanced binary tree as described by Knuth vol. 3 p.452 ff.
  27. >
  28. >Is this 1) reasonable and 2) fast?
  29.  
  30. I generally hate the linked-list-of-lines technique.
  31. For lots of good ideas, see The Craft of Text Editing, by Craig Finseth.
  32.  
  33. Probably the nest is the paged buffer gap.  You break the text into
  34. a series of pages, each of which is managed by a buffer-gap system.
  35. You can read the text in a page at a time and build the tree as you do it.
  36. If you don't edit, the text is basically contiguous in memory.  If you
  37. edit it, only the pages that hold the data are disturbed.  Using
  38. fixed-size pages improves memory fragmentation considerably.
  39.  
  40. What I'd do is in the extra info per page, store the number of newlines
  41. in the page.  Then use the standard technique in the tree of
  42. marking each node with the number of newlines in its left subtree
  43. to let you find the page that holds a given newline (the start of a
  44. given line) quickly, followed by which linear search is fine in
  45. a finite-sized page.  That lets you find a given line number very
  46. quickly.
  47.  
  48. If you do line-wrapping, and the display width is constant, you can do the
  49. same for visible lines.  Count a newline every time you have a hard newline
  50. or reach 80 characters (or whatever).  It sort of breaks down if the
  51. window keeps changing size, though.  To scroll backwards, you'll have to find
  52. the previous line's start and work forward from there to figure out where the
  53. visible tail of it starts.
  54.  
  55. Don't forget to look at a variety of balanced trees.  I like red-black trees,
  56. myself.  Then there are B-tree-like variants.
  57. -- 
  58.     -Colin
  59.